package com.cong._56;

import java.util.LinkedList;
import java.util.List;

class Solution {
    public int[][] merge(int[][] intervals) {
        LinkedList<Integer> list = new LinkedList<>();
        for (int[] itv: intervals) {
            int left = itv[0];
            int right = itv[1];
            if (list.size() == 0) {
                list.add(left);
                list.add(right);
                continue;
            }/*list 为空时直接添加*/

            // list 不为空时进行比较
            int lInsert = list.size();
            int rInsert = lInsert;
            int i = 0;
            for(;i < list.size();i++) {
                if(list.get(i) >= left) {
                    lInsert = i;
                    break;
                }
            }
            for(;i < list.size();i++) {
                if(list.get(i) > right) {
                    rInsert = i;
                    break;
                }
            }


            boolean banLeft = (lInsert & 1) == 1;
            boolean banRight = (rInsert & 1) == 1;
            // insert left and right
            list.add(lInsert, left);
            list.add(rInsert + 1, right);
            System.out.println(list + "; " + banLeft +"; " + banRight + "; " + lInsert + ": " + rInsert);

            int removeCount = rInsert - lInsert + (banLeft ? 1: 0) + (banRight ? 1: 0);
            int startIndex = banLeft ? lInsert : lInsert + 1;

            for (int remove = 0;remove < removeCount;remove++) {
                list.remove(startIndex);
            }

        }
        int[][] r = new int[list.size() / 2][];
        for(int i =0;i < list.size();i+=2) {
            r[i/2] = new int[] {list.get(i), list.get(i+1)};
        }
        return r;
    }
}
